// https://leetcode.cn/problems/search-a-2d-matrix/
#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
		int row = matrix.size();
		int col = matrix[0].size();
		int left = 0;
		int right = row * col - 1;
		int mid;
		while(left <= right){
			mid = (left + right) / 2;
			int num = matrix[mid/col][mid%col];
			cout << mid << " " << num << endl;
			if(num > target){
				right = mid - 1;
			}else if(num == target){
				return true;
			}else{
				left = mid + 1;
			}
		}
		
		return false;
		
		/*
		int m = matrix.size(), n = matrix[0].size();
        int low = 0, high = m * n - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int x = matrix[mid / n][mid % n];
            if (x < target) {
                low = mid + 1;
            } else if (x > target) {
                high = mid - 1;
            } else {
                return true;
            }
        }
        return false;

		*/
    }
};

int main(){
	// vector<vector<int>> matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
	vector<vector<int>> matrix = {{1,3}};
	// vector<vector<int>> matrix = {{1},{3}};
	Solution so;
	if(so.searchMatrix(matrix, 3)){
		cout << "find" << endl;
	}else{
		cout << "not" << endl;
	}
	return 0;
}